The present invention relates to transmission and switching of data packets through computer networks, such as scheduled packet switching systems, and more particularly to automatic scheduling of data flows.
So-called “converged” computer networks carry a mixture of traffic types, such as data, telephone (voice) and video. Some of this traffic is time-sensitive, and other of the traffic is not time-sensitive. For example, a converged local area network (LAN) can include a variety of hosts, such as workstations, IP telephones, storage servers, print servers, web servers, telephony servers (PBXs) and other endpoints. The LAN typically includes switches, routers, etc. (collectively “switches”), links between the switches and other network elements that interconnect the workstations, IP telephones, servers, etc. Timely delivery of packets that carry voice information between IP telephones and telephony servers is important to providing high-quality voice signals. Similarly, video and other time-sensitive packets must be delivered without delay. On the other hand, delays are tolerable in the delivery of normal computer data.
Some networks are operated as “real-time network scheduled packet routing systems” (or simply “scheduled networks”), so time-sensitive packets can be delivered without delay or jitter. One such system, described in U.S. Pat. No. 6,556,564, essentially reserves recurring time slots (“appointments”) at “schedule-aware” switches for each time-sensitive stream of packets (called a “scheduled data flow”) between a pair of endpoints. When an application program executing on a host connected to the network wishes to establish a path to another host for delivering a time-sensitive stream of packets, the application sends a request to a “scheduling agent” to establish a scheduled data flow. The path between the hosts (endpoints) includes one or more switches, a respective link between each pair of switches along the path and ingress and egress ports where the links terminate at the switches. The switches forward packets received on the ingress ports to the egress ports. A network can carry many crisscrossed scheduled data flow paths.
Each egress port has an associated schedule, in which individual repeating appointments can be made to reserve the egress port on a periodic basis for a particular scheduled data flow between a particular pair of endpoints. Reserving the egress port also reserves resources (within the switch) that are used to pass data received on an ingress port to the egress port. The scheduling agent makes the appointments (reserves the egress ports of the switches) along the path and coordinates the times of the appointments, such that (to the extent possible) when a packet is expected to be received on an ingress port of a switch, the appropriate egress port on the switch is reserved for the scheduled data flow. Thus, the packet can be forwarded by the switch without queuing the packet within the switch. Non-scheduled traffic that would otherwise be sent out the egress port is held off (queued within the switch), so the non-scheduled traffic does not interfere with the scheduled data flow.
In an ideally scheduled path, all egress ports along the path from one endpoint to the other endpoint are scheduled such that each egress port is reserved at a time that is equal to the reservation time of the immediately preceding egress port along the path, plus propagation time of a packet from the preceding egress port. Thus, a packet can traverse the path, from one endpoint to the other endpoint, without any queuing delay within any switch along the path. Due to the sequential nature of the reservation times along the path, the term “sequence” is used synonymously with “schedule” elsewhere in this disclosure.
During appointment times that are not reserved for any scheduled data flow, and during reserved appointments during which the switch does not receive a packet of the scheduled data flow, the switch routes non-scheduled traffic on a best-effort basis, as in more traditional switches. The switches can detect unused reserved appointments. For example, if the beginning of a packet does not arrive at a switch within a predetermined amount of time after the beginning of an appointment, the switch can conclude that no scheduled packet will be received during that appointment.
Scheduled networks ensure jitter-free delivery of time-sensitive packets while providing traditional best-effort delivery of non-time-sensitive packets. However, only application programs that explicitly request scheduled data flows receive this expedited service. These application programs must, therefore, be written to make these requests. Furthermore, to make application programs potable (i.e. capable of being used with scheduled networks and more traditional networks that do not include scheduling agents and schedule-aware switches), the application programs must be written to ascertain the kind of networks they operate with and make (or not make) requests for scheduled data handling, as appropriate. In addition, the performance of many existing (legacy) application programs would be improved by utilizing scheduled data flows, but these programs lack logic to request such service.
In addition, scheduled networks, and traditional best-effort networks, cannot be heavily utilized for non-time-sensitive traffic, without queuing packets within the switches. Heavy utilization is desirable, in that it is a cost-effective use of network elements. However, the consequential packet queuing consumes resources within many or all of the switches, and it causes delays in the delivery of the packets.
Some network owners would appreciate network elements that can automatically provide scheduled data flows to time-sensitive data streams, without explicit requests to do so from application programs.